package codeRandomThoughts.Test115不同的子序列;

import java.util.Arrays;

//尝试一维数组
public class Solution2 {
    public int numDistinct(String s, String t) {
        char[] chatT = t.toCharArray();
        char[] charS = s.toCharArray();

        //dp[i][j]:T(0~i-1)在S(0~j-1)中出现的次数
        int[] dp = new int[charS.length + 1];
        int[] tem = new int[charS.length + 1];

        //初始化
        //空集是所有字符串的子集,即他在任何字符串中都能出现一次
        for (int j = 0; j <= charS.length; j++) {
            tem[j] = 1;
        }

        for (int i = 1; i <= chatT.length; i++) {
            for (int j = 1; j <= charS.length; j++) {
                if (chatT[i - 1] == charS[j - 1]) {
                    //两种情况
                    //考虑j-1位置的元素
                    //和不考虑j-1位置的元素
                    dp[j] = tem[j - 1] + dp[j - 1];
                } else {
                    dp[j] = dp[j - 1];
                }
            }
            tem = dp.clone();
        }

        return dp[charS.length];
    }
}
